package sorter

import "math/rand"

// BubbleSort 冒泡排序是通过多次遍历数组，每次比较相邻元素并在顺序错误时交换它们，将较大（或较小）元素逐步“冒泡”到数组末端，从而实现排序的简单算法。
func BubbleSort(values []int) {
	n := len(values)
	// 外层循环：控制排序轮数
	for i := 0; i < n-1; i++ {
		// 内层循环：比较相邻元素
		for j := 0; j < n-i-1; j++ {
			// 如果前一个比后一个大，则交换
			if values[j] > values[j+1] {
				values[j], values[j+1] = values[j+1], values[j]
			}
		}
	}
}

func BubbleSortGeneric[T any](arr []T, less func(T, T) bool) {
	n := len(arr)
	for i := 0; i < n-1; i++ {
		for j := 0; j < n-i-1; j++ {
			if less(arr[j], arr[j+1]) {
				arr[j], arr[j+1] = arr[j+1], arr[j]
			}
		}
	}
}

// QuickSort 使用递归实现快速排序
func QuickSort(arr []int) []int {
	// 如果数组长度小于等于1，直接返回（递归终止条件）
	if len(arr) <= 1 {
		return arr
	}

	// 选择基准，这里选择最后一个元素作为 pivot
	pivot := arr[len(arr)-1]
	var left, right []int

	// 遍历除 pivot 外的元素
	for i := 0; i < len(arr)-1; i++ {
		if arr[i] <= pivot {
			left = append(left, arr[i]) // 小于等于 pivot 放左边
		} else {
			right = append(right, arr[i]) // 大于 pivot 放右边
		}
	}

	// 递归排序左右部分，然后合并结果：左 + pivot + 右
	return append(append(QuickSort(left), pivot), QuickSort(right)...)
}

// QuickSortGeneric 通用的快速排序函数
// 参数：
//   - arr: 待排序的切片（类型为任意，但必须约束为 comparable 或你指定的类型）
//   - less: 一个匿名函数（闭包），用于定义元素比较规则，返回 a 是否应排在 b 前面
func QuickSortGeneric[T any](arr []T, less func(a, b T) bool) {
	// 内部使用递归的辅助函数，传入左右边界
	var quickSort func(low, high int)
	quickSort = func(low, high int) {
		if low >= high {
			return // 递归终止
		}

		// 选择基准（这里选最后一个元素 arr[high]）
		pivot := arr[high]
		i := low // i 是小于 pivot 的区域的右边界

		// 分区操作（Partition）
		for j := low; j < high; j++ {
			// 如果当前元素应排在 pivot 前面（根据 less 函数定义的规则）
			if less(arr[j], pivot) {
				arr[i], arr[j] = arr[j], arr[i] // 交换
				i++
			}
		}

		// 最后将 pivot 放到正确的位置，即 i 的位置
		arr[i], arr[high] = arr[high], arr[i]

		// 递归排序左半部分和右半部分
		quickSort(low, i-1)
		quickSort(i+1, high)
	}

	// 调用内部递归排序函数，对整个切片排序
	quickSort(0, len(arr)-1)
}

// ShuffleSlice 对给定的切片进行随机打乱操作
// 使用Fisher-Yates洗牌算法实现，确保每种排列的概率相等
//
// 参数:
//
//	slice []T - 需要被打乱的切片，支持任意类型
//
// 返回值:
//
//	无返回值，直接修改传入的切片
func ShuffleSlice[T any](slice []T) {
	// 从切片末尾开始向前遍历
	n := len(slice)
	for i := n - 1; i > 0; i-- {
		// 在[0, i]范围内随机选择一个索引
		j := rand.Intn(i + 1)
		// 交换当前元素与随机选中的元素
		slice[i], slice[j] = slice[j], slice[i]
	}
}
